package 纯数组;

import com.alibaba.fastjson.JSON;

import java.util.Random;

/**
 * @description:
 * @author: 小白白
 * @create: 2021-10-13
 **/

public class No384打乱数组 {

    /**
     * 给你一个整数数组 nums ，设计算法来打乱一个没有重复元素的数组。
     * 实现 Solution class:
     * Solution(int[] nums) 使用整数数组 nums 初始化对象
     * int[] reset() 重设数组到它的初始状态并返回
     * int[] shuffle() 返回数组随机打乱后的结果
     *  
     * 示例：
     * 输入
     * ["Solution", "shuffle", "reset", "shuffle"]
     * [[[1, 2, 3]], [], [], []]
     * 输出
     * [null, [3, 1, 2], [1, 2, 3], [1, 3, 2]]
     * 解释
     * Solution solution = new Solution([1, 2, 3]);
     * solution.shuffle();    // 打乱数组 [1,2,3] 并返回结果。任何 [1,2,3]的排列返回的概率应该相同。例如，返回 [3, 1, 2]
     * solution.reset();      // 重设数组到它的初始状态 [1, 2, 3] 。返回 [1, 2, 3]
     * solution.shuffle();    // 随机返回数组 [1, 2, 3] 打乱后的结果。例如，返回 [1, 3, 2]
     *  
     * 提示：
     * 1 <= nums.length <= 200
     * -106 <= nums[i] <= 106
     * nums 中的所有元素都是 唯一的
     * 最多可以调用 5 * 104 次 reset 和 shuffle
     */

    static class Solution {

        /**
         * 此题一定要用洗牌算法,它才是绝对公平的算法,保证了每张牌移动到任一位的概率都是 1/n
         * 洗牌算法有点像冒泡排序,它的空间是在慢慢缩小的
         */

        private int[] originArr;
        private Random random = new Random();
        private int[] arr;

        public Solution(int[] nums) {
            this.originArr = nums.clone();
        }

        public int[] reset() {
            int[] tempArr = originArr;
            originArr = originArr.clone();
            return tempArr;
        }

        public int[] shuffle() {
            this.arr = originArr.clone();
            // 每次都返回一个随机数组
            for (int i = 0; i < arr.length; i++) {
                swap(i, getRandomByRand(i, arr.length));
            }
            return arr;
        }

        private int getRandomByRand(int min, int max) {
            return random.nextInt(max - min) + min;
        }

        private void swap(int i1, int i2) {
            if (arr[i1] == arr[i2]) {
                return;
            }
            // 因为没有重复元素,所以可以使用位运算
            arr[i1] ^= arr[i2];
            arr[i2] ^= arr[i1];
            arr[i1] ^= arr[i2];
        }

    }

    public static void main(String[] args) {
        int[] arr = {1,2,3};
        Solution solution = new Solution(arr);
        int[] shuffle = solution.shuffle();
        System.out.println(JSON.toJSONString(shuffle));
    }

}
